class Node {
    int data;
    Node prev; // 前驱指针
    Node next; // 后继指针

    public Node(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

public class DoublyLinkedList {
    private Node head;
    private Node tail;
    private int size;

    public DoublyLinkedList() {
        head = tail = null;
        size = 0;
    }

    // 头插法（双向循环）
    public void addHead(int data) {
        Node newNode = new Node(data);
        if (size == 0) { // 空链表
            newNode.next = newNode;
            newNode.prev = newNode;
            head = tail = newNode;
        } else { // 非空链表
            newNode.next = head;
            newNode.prev = tail;
            head.prev = newNode;
            tail.next = newNode;
            head = newNode;
        }
        size++;
    }

    // 尾插法（双向循环）
    public void addTail(int data) {
        Node newNode = new Node(data);
        if (size == 0) { // 空链表
            newNode.next = newNode;
            newNode.prev = newNode;
            head = tail = newNode;
        } else { // 非空链表
            tail.next = newNode;
            newNode.prev = tail;
            newNode.next = head;
            head.prev = newNode;
            tail = newNode;
        }
        size++;
    }

    // 删除指定值的节点（双向循环优化）
    public void deleteNode(int data) {
        if (size == 0) {
            System.out.println("链表为空");
            return;
        }

        Node current = head;
        do {
            if (current.data == data) {
                if (size == 1) { // 只有一个节点
                    head = tail = null;
                } else {
                    // 处理头节点
                    if (current == head) {
                        head = head.next;
                        head.prev = tail;
                        tail.next = head;
                    }
                    // 处理尾节点
                    else if (current == tail) {
                        tail = tail.prev;
                        tail.next = head;
                        head.prev = tail;
                    }
                    // 处理中间节点
                    else {
                        current.prev.next = current.next;
                        current.next.prev = current.prev;
                    }
                }
                size--;
                return;
            }
            current = current.next;
        } while (current != head);

        System.out.println("未找到数据为" + data + "的节点");
    }

    // 反转链表（双向循环专用）
    public void reverse() {
        if (size <= 1) return;

        Node current = head;
        Node temp = null;
        do {
            temp = current.prev;
            current.prev = current.next;
            current.next = temp;
            current = current.prev;
        } while (current != head);

        if (temp != null) {
            head = temp.prev;
        }
    }

    // 打印链表（正向）
    public void printForward() {
        if (size == 0) {
            System.out.println("[]");
            return;
        }

        System.out.print("[");
        Node current = head;
        do {
            System.out.print(current.data);
            if (current.next != head) {
                System.out.print(" <-> ");
            }
            current = current.next;
        } while (current != head);
        System.out.println("]");
    }

    // 打印链表（反向）
    public void printBackward() {
        if (size == 0) {
            System.out.println("[]");
            return;
        }

        System.out.print("[");
        Node current = tail;
        do {
            System.out.print(current.data);
            if (current.prev != tail) {
                System.out.print(" <-> ");
            }
            current = current.prev;
        } while (current != tail);
        System.out.println("]");
    }

    public static void main(String[] args) {
        DoublyLinkedList list = new DoublyLinkedList();

        // 初始化操作演示
        System.out.println("初始化链表");
        list.addHead(15);
        list.addHead(14);
        list.addHead(13);
        list.addTail(21);
        list.addTail(22);
        list.addTail(23);
        list.printForward();  // [13 <-> 14 <-> 15 <-> 21 <-> 22 <-> 23]
        System.out.println("长度：" + list.size); // 6

        // 删除节点演示
        System.out.println(" 删除数据为13的节点");
                list.deleteNode(13);
        list.printForward();  // [14 <-> 15 <-> 21 <-> 22 <-> 23]
        System.out.println("长度：" + list.size); // 5

        System.out.println(" 删除数据为23的节点");
                list.deleteNode(23);
        list.printForward();  // [14 <-> 15 <-> 21 <-> 22]
        System.out.println("长度：" + list.size); // 4

        // 反转操作演示
        System.out.println(" 反转链表");
                list.reverse();
        list.printForward();  // [22 <-> 21 <-> 15 <-> 14]
        list.printBackward(); // [14 <-> 15 <-> 21 <-> 22]
    }
}